
// 34.在排序数组中查找元素的第一次和最后一个位置

class Solution {

    int _lower_bound(vector<int>& nums , int tar)
    {
        int l = -1, r = nums.size();
        while(l + 1 < r)
        {
            int mid = l + (r - l)/2;
            if(nums[mid] >= tar) r = mid;
            else l = mid;
        }            
        return r;
    }
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        // 二分查找
        int n = nums.size();
        int beg = _lower_bound(nums , target);
        int end = _lower_bound(nums , target + 1);

        return (beg < n && nums[beg] == target) ? vector<int>{beg , end - 1} : vector<int>{-1 , -1};
    }
};